Many display systems present images by generating output signals representing thousands of picture elements or "pixels." The color and intensity of each pixel is controlled by a respective output signal that is generated according to associated pixel data.
Many applications attempt to generate realistic displays of three-dimensional objects by forming pixel data that represent a variety of visual characteristics for object surfaces such as roughness, patterns, color and shading. One technique that is used is known as texture mapping. Conceptually, this technique maps textures onto surfaces and then projects onto a screen the mapped textures together with the surfaces. The mapping and projecting processes involve transformations from one space to another.
Generally, a texture is defined in a texture space having a two-dimensional coordinate system (u,v). The texture comprises textural elements or "texels." The surfaces of an object are defined in an object space having a three-dimensional coordinate system (x',y',z'). The resultant display or image is defined in an image space having a two-dimensional coordinate system (x,y). In concept, texture mapping transforms the texture defined in texture space onto a surface defined in the object space and then projects the transformed texture onto a display screen in the image space. This process is not unlike applying a decal, which represents the texture, onto an object and then projecting the applied decal onto a display surface. The content of pixel data formed to represent the mapped and projected texture is a function of the mapping and projecting transformations as well as the texture definition itself.
One problem that is encountered during texture mapping is aliasing. The cause of aliasing may be understood by first visualizing a texture or pattern mapped onto a surface that is parallel to the image space. The projection of the texture onto the image space (x,y) is a uniformly scaled replica of the texture definition in texture space (u,v). As the surface in object space (x',y',z') rotates, the projection of the pattern onto image space is compressed nonuniformly. The amount of compression increases as the angle between image space and the surface normal departs from ninety degrees and, for perspective projections, it also increases with increasing distance from the image space. The consequence of increased compression is that larger areas of the texture are projected onto individual pixels in image space. If the amount of compression is great enough, distinctive textural features are projected into single pixels. The net effect is aliasing. The spatial sampling frequency of the pixels in image space is not high enough to accurately represent the higher spatial frequencies in the compressed texture.
Aliasing may be avoided by filtering the texture that is projected into each pixel. Preferably, the filtering is accomplished by applying a space-variant filter to the texture definition.
One way in which a space-variant filter may be applied is to map an individual pixel in image space (x,y) onto the texture, forming a pixel "footprint" in texture space (u,v), and then generate pixel data by filtering or averaging the texels in the pixel footprint. This approach requires considerable computational resources because pixel data must be generated for many thousands, perhaps millions, of pixels and because many thousands, perhaps millions, of texels must be filtered for individual pixels.
Another way, which avoids or at least reduces aliasing effects and requires considerably lower computation resources, uses filtered representations of the texture. One type of filtered representations is described in Dungan, et al., "Texture Tile Considerations for Raster Graphics," Computer Graphics, vol. 12, no. 3, August 1978, pp. 130-134. Another type of filtered representations, known as a MIP map, is discussed in Williams, "Pyramidal Parametrics," Computer Graphics, vol. 17, no. 3, July 1983, pp. 1-11. The MIP map is a pyramidal structure in which the bottom level, level 0, contains texels from a square area of the texture definition itself and each successively higher level contains one-fourth the number of texels. For example, each texel in level d+1 corresponds to four texels in level d. Stated differently, the spatial resolution of the texture for each dimension in level d+1 is one-half the spatial resolution for each dimension in level d. The filtered representations may be formed such that the spatial resolution of the texture in successive levels differs by any convenient factor.
An appropriate amount of filtering is applied to a given pixel by selecting an appropriate level in the filtered representations. The selected level need not be an integer. The fractional part of a selected level may be realized by trilinear interpolation of texels in adjacent levels.
Several methods for selecting the appropriate level are known. One method selects the level based on the longest dimension of the pixel footprint in texture space. Another method, which maps circular pixels onto elliptical areas in texture space, selects the level based on the average diameter of the ellipse. Other methods, which map square pixels onto curvilinear polygons in texture space, select levels based on values derived from the length of one or more sides of the polygons. Yet another method selects the level from values based on partial derivatives of the pixel mapping in texture space with respect to the image space. An example of a device that uses partial derivatives to select a level is disclosed in U.S. Pat. No. 5,097,427, which is incorporated herein by reference in its entirety.
The selection of level is important. If the selected level is too high, the resultant image will be blurred. If the selected level is too low, the resultant image will contain aliasing. As a result, the level should be selected for each pixel in the image. Unfortunately, known methods for selecting the level all require considerable processing resources.